package stacktest;

import java.util.Stack;

public class Test {
    /**
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
     * 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列
     * @param pushV
     * @param popV
     * @return
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        if(pushV.length==0||popV.length==0)
            return false;
        Stack<Integer> stack = new Stack<>();
        int j=0;//遍历popV数组
        for(int i=0;i<pushV.length;i++){
            int val=pushV[i];
            stack.push(val);
            while(!stack.empty()&&j<popV.length&&stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    /**
     * 有效的括号
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(ch=='('||ch=='{'||ch=='['){
                stack.push(ch);
            }else{
                if(stack.empty()){//栈是空的，但遇到右括号
                    return false;
                }
                char c =stack.peek();
                if(c=='('&&ch==')'||c=='{'&&ch=='}'||c=='['&&ch==']'){
                    stack.pop();//括号匹配
                }else{
                    return false;//括号不匹配
                }
            }

        }
        if(!stack.empty()){
            return false;
        }
        return true;

    }
    /**
     * 逆波兰表达式求值
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        //1.遍历这个字符串如果是数字字符串入栈，不是出栈两个数字
        for (int i = 0; i < tokens.length; i++) {
            String x =tokens[i];
            if(!isOperation(x)){
                stack.push(Integer.parseInt(x));

            }else{
                int num2= stack.pop();
                int num1= stack.pop();

                switch (x){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }

            }
            
        }
        return stack.pop();
    }
    private boolean isOperation(String s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))
            return true;
        return false;
    }
    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);
        int x = stack.pop();
        System.out.println(x);
        x = stack.pop();
        System.out.println(x);
        x=stack.peek();//获取栈顶元素但不删除
        System.out.println(x);
        x=stack.pop();//获取栈顶元素并且删除
        System.out.println(x);
        boolean flg=stack.empty();
        System.out.println(flg);
        x=stack.pop();
        flg=stack.empty();
        System.out.println(flg);
    }
    public static void main1(String[] args) {
        Stack<Integer> stack=new Stack<>();
        stack.push(12);
        stack.push(23);
        stack.push(34);
        stack.push(45);
        int x = stack.pop();
        System.out.println(x);
        x = stack.pop();
        System.out.println(x);
        x=stack.peek();//获取栈顶元素但不删除
        System.out.println(x);
        x=stack.pop();//获取栈顶元素并且删除
        System.out.println(x);
        boolean flg=stack.empty();
        System.out.println(flg);
        x=stack.pop();
        flg=stack.empty();
        System.out.println(flg);


    }
}
